#include "cgraph.h"
#include <iostream>
#include <queue>
#include <memory>
#include <list>

CGraph::CGraph(int iCapacity, bool bVec):
    m_iCapacity(iCapacity), bVec(bVec)
{
    init(m_iCapacity);
}

CGraph::~CGraph ()
{
    freeVertex();
}

bool CGraph::addVertex (VertexTag tag)
{
    auto iter = m_tagToIndex.find (tag);
    if( iter != m_tagToIndex.end () )
    {
        cout << "Add vertex: "<< tag << "error!";
        return false;
    }

    m_tagToIndex[tag]  = m_vecVertexSet.size();
    m_vecVertexSet.push_back (new VertexNode(tag));
    return true;
}

void CGraph::freeVertex ()
{
    for(size_t i = 0; i < m_vecVertexSet.size (); ++i)
        delete m_vecVertexSet[i];
}

void CGraph::init (int iCapacity)
{
    m_vecVertexSet.reserve (iCapacity);

    m_vecMatrix.resize (iCapacity);
    for(int i = 0; i < iCapacity; ++i)
    {
        m_vecMatrix[i].resize(iCapacity);
        for(int j = 0; j < iCapacity; ++j)
            m_vecMatrix[i][j] = EDGEINFO_MAX;
    }
}

void CGraph::resetGraph (int iCapacity)
{
    //重置标识映射索引集
    m_tagToIndex.clear ();
    //释放顶点
    freeVertex();
    //重置矩阵
    m_vecMatrix.clear ();

    if(iCapacity)
        init(iCapacity);
    else
        init(m_iCapacity);
}

bool CGraph::connectVertex (VertexTag tagA, VertexTag tagB, EdgeInfo info)
{
    auto iterA = m_tagToIndex.find (tagA);
    if( iterA == m_tagToIndex.end () )
        return false;

    auto iterB = m_tagToIndex.find (tagB);
    if( iterB == m_tagToIndex.end () )
        return false;

    //对与无向图而言，两个顶点都需要指向边
    //有向图则不需要，而遵从tagA指向tagB

    size_t unIndexA = iterA->second;
    size_t unIndexB = iterB->second;

    VertexNode *pVertexA = m_vecVertexSet[unIndexA];
    VertexNode *pVertexB = m_vecVertexSet[unIndexB];

    EdgeNode *pEdge = new EdgeNode(pVertexB);
    //顶点中添加这个边
    pVertexA->Edge.push_back (pEdge);
    //pVertexB->PreTag.push_back (unIndexA);

    //设置矩阵
    m_vecMatrix[unIndexA][unIndexB] = info;

    if( bVec )
    {
        //无向图
        EdgeNode *pEdgeTemp = new EdgeNode(pVertexA);
        pVertexB->Edge.push_back (pEdgeTemp);
        //pVertexA->PreTag.push_back (unIndexB);

        //设置矩阵
        m_vecMatrix[unIndexB][unIndexA] = info;
    }

    return true;
}

void CGraph::printMatrix ()
{
    if(!vecMatrix)
        vecMatrix = &m_vecMatrix;
    size_t i = 0;

    char cstr[12] = {0,};
    cout << " =";
    for(; i < vecMatrix->size (); ++i)
    {
        sprintf(cstr, "%10d", i);
        cout << cstr << "=";
    }
    cout << endl;

    for(i = 0; i < vecMatrix->size (); ++i)
    {
        cout << i << "=";
        for(size_t j = 0; j < (*vecMatrix)[i].size(); ++j)
        {
            sprintf(cstr, "%010d", (*vecMatrix)[i][j]);
            cout << cstr  << "=";
        }

        cout << endl;
    }
}

void CGraph::printVertexInfo ()
{
    for(size_t i = 0; i < m_vecVertexSet.size (); ++i)
    {
        cout << "顶点标识: " << static_cast<int>(m_vecVertexSet[i]->vTag)
             << "状态: " <<  static_cast<int>(m_vecVertexSet[i]->status)
             << "层级: " << m_vecVertexSet[i]->nLevel
             << endl;

        //打印边集
        for(size_t j = 0; j < m_vecVertexSet[i]->Edge.size(); ++j)
        {
            cout << "第" << j << "边指向：" << static_cast<int>(m_vecVertexSet[i]->Edge[j]->pNextVertex->vTag)
                 << "标识"
                 << endl;
        }
    }
}

void CGraph::BFS(VertexTag vTag)
{
    //从索引m_tagToIndex.begin()开始遍历
    //遍历的是begin()顶点所连通的图

    size_t szIndex = m_tagToIndex[vTag];

    m_vecVertexSet[szIndex]->status = GRAY;
    m_vecVertexSet[szIndex]->nLevel = 0;
    m_vecVertexSet[szIndex]->PreTag = VertexNull;

    queue<VertexTag> Q;

    Q.push (vTag);
    while(!Q.empty ())
    {
        vTag = Q.front ();
        Q.pop ();
        szIndex = m_tagToIndex[vTag];
        VertexNode *pPre = m_vecVertexSet[szIndex];
        //m_vecVertexSet[szIndex]->Edge
        for(auto iter = pPre->Edge.begin();
            iter != pPre->Edge.end();
            ++iter)
        {
            VertexNode *pVertex = (*iter)->pNextVertex;
            if( pVertex && pVertex->status == WHITE )
            {
                pVertex->status = GRAY;
                pVertex->nLevel = pPre->nLevel + 1;
                pVertex->PreTag = pPre->vTag;
                Q.push (pVertex->vTag);
            }
        }
        pPre->status = BLACK;
        cout << static_cast<int>(pPre->vTag) << " ";
    }

    cout << endl;
}

void CGraph::BFS_ (VertexTag vTag, int nLvl)
{
    //递归实现
    size_t szIndex = m_tagToIndex[vTag];

    VertexNode *pCurrent = m_vecVertexSet[szIndex];
    pCurrent->nLevel = nLvl;
    pCurrent->status = BLACK;
    cout << pCurrent->nLevel << " ";
    cout << static_cast<int>(pCurrent->vTag) << " ";
    cout << endl;

    for(auto iter = pCurrent->Edge.begin();
        iter != pCurrent->Edge.end();
        ++iter)
    {
        VertexNode *pVertex = (*iter)->pNextVertex;
        if( pVertex && pVertex->status == WHITE )
        {
            pVertex->status = GRAY;
            pVertex->nLevel = pCurrent->nLevel + 1;
            pVertex->PreTag = pCurrent->vTag;
            BFS_(pVertex->vTag, pVertex->nLevel);
        }
    }
}

void CGraph::LimitPath (VertexTag vTag1, VertexTag vTag2)
{
    // vTag1 => vTag2

    size_t szIndex = m_tagToIndex[vTag1];

    VertexNode *pVertex = m_vecVertexSet[szIndex];

    while(pVertex)
    {
        cout << static_cast<int>(pVertex->vTag) << " ";

        if(pVertex->vTag == vTag2)
        {
            cout << "路径完毕!" << endl;
            return;
        }else
        if(pVertex->PreTag == VertexNull)
        {
            cout << "没有最短路径，可能无连通!" << endl;
            return;
        }


        szIndex = m_tagToIndex[pVertex->PreTag];
        pVertex = m_vecVertexSet[szIndex];
    }

    cout << endl;
}

void CGraph::LimitPath_ (VertexTag vTag1, VertexTag vTag2)
{
    if(vTag1 == vTag2)
        cout << static_cast<int> (vTag2) << " ";
    else if(m_vecVertexSet[m_tagToIndex[vTag1]]->PreTag == VertexNull)
        cout << "no path from " << static_cast<int> (vTag1) << " to " << static_cast<int> (vTag2) << " exists.";
    else
    {
        cout << static_cast<int> (vTag1) << " ";
        LimitPath_ (m_vecVertexSet[m_tagToIndex[vTag1]]->PreTag, vTag2);
    }
}

void CGraph::DFS ()
{
    //暂时不需要对顶点初始化

    for(auto iter = m_vecVertexSet.begin ();
        iter != m_vecVertexSet.end ();
        ++iter)
    {
        if((*iter)->status == WHITE)
            DFS_VISIT ((*iter)->vTag);
    }
}

int CGraph::StopTag = 0;

void CGraph::DFS_VISIT (VertexTag tag)
{
    StopTag += 1;

    size_t szIndex = m_tagToIndex[tag];
    VertexNode *pVertex = m_vecVertexSet[szIndex];

    pVertex->nLevel = StopTag;
    pVertex->status = GRAY;

    cout << "---顶点: " << static_cast<int>(pVertex->vTag) << " "
         << "步级: " << pVertex->nLevel << " "
         << "状态: " << static_cast<int>(pVertex->status)
         << endl;

    for(auto iter = pVertex->Edge.begin (); iter != pVertex->Edge.end(); ++iter)
    {
        VertexNode *pNextVertex = (*iter)->pNextVertex;
        if( pNextVertex->status == WHITE )
        {
            pNextVertex->PreTag = pVertex->vTag;
            DFS_VISIT (pNextVertex->vTag);
        }
    }

    pVertex->status = BLACK;
    pVertex->nLevel = StopTag += 1;

    cout << "顶点: " << static_cast<int>(pVertex->vTag) << " "
         << "步级: " << pVertex->nLevel << " "
         << "状态: " << static_cast<int>(pVertex->status)
         << endl;
}

int CGraph::Prim ()
{
    size_t szSize = m_vecVertexSet.size ();
    if( !szSize )
        return 0;

    INDEX_TO_PATH_INFO *pPathInfo = new INDEX_TO_PATH_INFO[szSize];

    size_t szCurPos = 0;

    //初始设置
    for(size_t i = 0; i < szSize; ++i)
    {
        //所有顶点都指为初始点
        pPathInfo[i].first = m_vecVertexSet[szCurPos]->vTag;
        //设置相应权值
        pPathInfo[i].second = m_vecMatrix[szCurPos][i];
    }

    pPathInfo[szCurPos].first = m_vecVertexSet[szCurPos]->vTag;
    pPathInfo[szCurPos++].second = 0; // 表示被选入mini树中

    EdgeInfo infoMin, ResultSum = 0;
    size_t szMinIndex;

    //酷似冒泡排序依次获取所需要的边，n-1条边
    //最先的顶点被确认，而冒泡排序则反之
    for(size_t i = szCurPos; i < szSize; ++i)
    {
        infoMin = EDGEINFO_MAX;
        szMinIndex = 0;

        ////////////////////
        //1.提供最小边
        //获得还没有被选入最小生成树的同时与最小的开销值与索引
        //保证了较小的开销
        for(size_t j = szCurPos; j < szSize; ++j)
        {
            if( pPathInfo[j].second != 0 && pPathInfo[j].second < infoMin )
            {
                infoMin = pPathInfo[j].second;
                szMinIndex = j;
            }
        }
        /////////////////////////
        //添加到总开销中
        ResultSum += infoMin;
        cout << "V" << static_cast<int>(pPathInfo[szMinIndex].first) << "-V" << szMinIndex << "=" << infoMin << endl;


        //////////////////////////
        //2.保证已经确定最佳路径的顶点不会再次被操作
        //使用选入mini tree
        pPathInfo[szMinIndex].second = 0;
        //////////////////////////


        /////////////////////////
        //3.使可发展分支顶点的数据为最新化
        //新的支点所能到达的顶点所需要的最小开销
        //保证了生成树的连通性
        for(size_t j = szCurPos; j < szSize; ++j)
        {
            if( m_vecMatrix[szMinIndex][j] < pPathInfo[j].second )
            {
                pPathInfo[j].second =   m_vecMatrix[szMinIndex][j];
                pPathInfo[j].first = szMinIndex;
            }
        }
        /////////////////////////
    }


    //这个时候pPathInfo里所需的就是最小生成树
    delete []pPathInfo;

    return ResultSum;
}

vector<shared_ptr<EdgeElement>> CGraph::getEdgeSet()
{
    vector<shared_ptr<EdgeElement>> vecEdgeSet;

    //边信息从矩阵中获得
    //有向图遍历全图
    //无向图遍历一部分
    //

    for(size_t i = 0; i <m_vecMatrix.size (); ++i)
    {
        //i => j
        //索引i 与索引j之间的开销

        size_t j = 0;

        //如果是无向图只读一半
        if( bVec )
        {
            //判断图存在自环，既顶点自己指向自己
            j = i;
            if( m_vecMatrix[i][j] !=  EDGEINFO_MAX )
            {
                vecEdgeSet.clear ();
                return vecEdgeSet; //返回空边集
            }
            //避免读中折线上的点
            ++j;
        }

        for( ; j <m_vecMatrix.size (); ++j )
        {
            //有权值
            if( m_vecMatrix[i][j] == EDGEINFO_MAX )
                continue;

            shared_ptr<EdgeElement> pElem = make_shared<EdgeElement>();
            pElem->Cash = m_vecMatrix[i][j];
            pElem->VertexPair.first = i;
            pElem->VertexPair.second = j;
            vecEdgeSet.push_back (pElem);
        }
    } // for

    return vecEdgeSet;
}

VertexTag CGraph::FindParent (const vector<VertexTag> &vecVertexParent, VertexTag vTag)
{
    if(vecVertexParent[m_tagToIndex[vTag]] == -1)
        return vTag;

    return FindParent(vecVertexParent, vecVertexParent[m_tagToIndex[vTag]] );
}

bool CGraph::IsVertexInPen (const vector<VertexTag> &vecVertexParent, shared_ptr<EdgeElement> pEdge)
{
    //判断是否有环路
    if(FindParent (vecVertexParent, pEdge->VertexPair.first) == FindParent (vecVertexParent, pEdge->VertexPair.second))
        return true;

    //若这条边相连，构成环路，则构成环路的两点必有且总有相同的前驱节点

    return false;
}

int CGraph::Kruskal ()
{
    vector<shared_ptr<EdgeElement>> vecEdgeSet = getEdgeSet ();
    //整理边，按值从小到大排序

    list<shared_ptr<EdgeElement>> listEdge(vecEdgeSet.begin (), vecEdgeSet.end());

    listEdge.sort ( [](shared_ptr<EdgeElement> E1, shared_ptr<EdgeElement> E2) -> bool{
        return *E1 < *E2;
    });

//    for(auto iter = listEdge.begin (); iter != listEdge.end (); ++iter)
//        cout << (*iter)->Cash << " ";
//        cout << endl;

//    vector<shared_ptr<EdgeElement>> vecEdgePath;
    EdgeInfo Sum = 0;
    size_t szIndex = 0;
    size_t szPathMax = m_vecVertexSet.size () - 1;

    vector<VertexTag> vecVertexParent(m_vecVertexSet.size (), -1);
    for(auto iter = listEdge.begin (); szIndex < szPathMax && iter != listEdge.end (); ++iter)
    {
        if( IsVertexInPen (vecVertexParent, *iter) )
            continue;

        //这个判断是因为获取边导致的，因为是从矩阵里获得，有向图与无向图边信息矩阵的读法不同所以导致
        if(bVec && vecVertexParent[m_tagToIndex[(*iter)->VertexPair.second]] != -1 )
            vecVertexParent[m_tagToIndex[(*iter)->VertexPair.first]] = (*iter)->VertexPair.second;
        else
            vecVertexParent[m_tagToIndex[(*iter)->VertexPair.second]] = (*iter)->VertexPair.first;

        //vecEdgePath.push_back (*iter);
        Sum += (*iter)->Cash;
        //又找到一条边
        ++szIndex;
    }

    for (auto  iter = vecVertexParent.begin (); iter != vecVertexParent.end (); ++iter) {
        cout << static_cast<int>(*iter) << " ";
    }

    return Sum;
}

void CGraph::Dijkstra ()
{
    //理解这个函数主要问题在当每一个顶点已经找到最佳的路径后
    //会得到其他几条新的路径，而这新的路径可能具有通往之前顶点的最短路径
    //一方面是发现新的顶点，一方面是具有的可能有性（构成改变之前顶点最短路径的可能）

    size_t sztSize = m_vecVertexSet.size ();
    vector<size_t> pVertexIndexArr(sztSize, 0); //存放顶点索引
    vector<EdgeInfo> pEdgeInfoArr(sztSize); //存放开销

    EdgeInfo Min;
    vector<Byte> byFinal(sztSize, 0);
    
    //初始化
    for(size_t i = 0; i < sztSize; ++i)
    {
        pEdgeInfoArr[i] = m_vecMatrix[0][i];
        pVertexIndexArr[i] = 0;
        byFinal[i] = 0;
    }

    pEdgeInfoArr[0] = 0;
    byFinal[0] = 1;//表示v0不需要求路径

    size_t k;
    for(size_t i = 1; i < sztSize; ++i) //求得sztSize个顶点的最短路径除0外
    {
        Min = EDGEINFO_MAX;
        //寻找与当前顶点最近的顶点
        for(size_t wIndex = 0; wIndex < sztSize; ++wIndex)
        {
            //已经找到的顶点则不需要寻找
            if(!byFinal[wIndex]
                    && pEdgeInfoArr[wIndex] < Min)
            {
                k = wIndex; // 确定最小索引
                Min = pEdgeInfoArr[wIndex]; // wIndex最小权值
            }
        }

        //标记已经找到，vk顶点不需要求路径
        byFinal[k] = 1;

        //更新顶点信息
        for(size_t wIndex = 0; wIndex < sztSize; ++wIndex)
        {
            //已经被确认的顶点不需要再比较
            if(!byFinal[wIndex]
                    //如果开销大于已经找到的最小开销与之前的
                    && pEdgeInfoArr[wIndex] > Min + static_cast<long long>(m_vecMatrix[k][wIndex]))
            {
                pEdgeInfoArr[wIndex] = Min + m_vecMatrix[k][wIndex];
                pVertexIndexArr[wIndex] = k;
            }
        } // for
    } // for

    for(size_t i = 0; i < sztSize; ++i)
    {
//        cout << static_cast<int>(byFinal[i]) << " ";
        cout << pVertexIndexArr[i] << " " << pEdgeInfoArr[i] << endl;
    }

}

void CGraph::Floyd ()
{
    size_t sztSize = m_vecVertexSet.size ();
    vector<vector<VertexTag>> vec2VertexTag(sztSize, vector<VertexTag>(sztSize));
    vector<vector<EdgeInfo>> vec2EdgeInfo(m_vecMatrix);
//    vec2EdgeInfo = m_vecMatrix.;

    for(int i = 0; i < sztSize; ++i)
    {
//        vec2VertexTag[i].resize(sztSize);
        for(int j = 0; j <sztSize; ++j)
        {
            vec2VertexTag[i][j] = j;
        }
    }

    for(int i = 0; i < sztSize; ++i)
    {
        for(int j = 0; j < sztSize; ++j)
        {
            for(int k = 0; k < sztSize;++k)
            {
                if( j != k && vec2EdgeInfo[j][k] > vec2EdgeInfo[j][i] + static_cast<long long>( vec2EdgeInfo[i][k]) )
                {
                    vec2EdgeInfo[j][k] = vec2EdgeInfo[j][i] + vec2EdgeInfo[i][k];
                    vec2VertexTag[j][k] = vec2VertexTag[j][i];
                }
            } // for
        } // for

        printMatrix(&vec2EdgeInfo);

        cout << "-------------------------------------" << endl;
    } // for
}


